/*
 * Copyright (c)e 2024-2024.Powered by 清明雨揽月
 * This software is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan
 * PSL v2.
 * You may obtain a copy of Mulan PSL v2 at:
 *          http://license.coscl.org.cn/MulanPSL2
 * THIS SOFTWARE IS PROVIDED ON AN 'AS IS' BASIS, WITHOUT WARRANTIES OF ANY
 * KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO
 * NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 * See the Mulan PSL v2 for more details.
 */

#include "look_up.h"
#include "iostream"

using namespace std;

void look_up::operate()
{
    _s_table.elem = &arr_unordered[0];
    _s_table.length = ARRAY_LENGTH;
    int index = search_seq(423);
    if (index == -1)
    {
        cout << "有序数组查找失败，返回值为：" << index << endl;
    }
    else
    {
        cout << "有序数组查找成功，成功元素下标为：" << index << endl;
    }
    _s_table.elem = &arr_ordered[0];
    index = search_bin(423);
    if (index == -1)
    {
        cout << "无序数组查找失败，返回值为：" << index << endl;
    }
    else
    {
        cout << "无序数组查找成功，成功元素下标为：" << index << endl;
    }
}

/**
 * int search_seq(int key)
 * 顺序查找，通过逐个关键字检查判断目标元素位置
 * @param key
 * @return
 */
int look_up::search_seq(const int key) const
{
    _s_table.elem[0] = key;
    int index = _s_table.length;
    for (index = _s_table.length; _s_table.elem[index] != key; --index);
    return index;
}

/**
 * int look_up(int key)
 * 折半查找，又称二分查找，仅适用于有序的顺序表
 * @param key
 * @return
 */
int look_up::search_bin(const int key) const
{
    int low = 0, high = _s_table.length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (_s_table.elem[mid] == key)
            return mid;
        if (_s_table.elem[mid] > key)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return -1;
}
